//
//  Lesson2.swift
//  AlgorithmSwift
//
//  Created by 李笑臣 on 2020/10/10.
//

import Cocoa

/**
 
 2. 两数相加
 
 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 示例：

 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 输出：7 -> 0 -> 8
 原因：342 + 465 = 807
 
 输入：(0 -> 1 -> 9 -> 4 -> 3) + (5 -> 6 -> 4)
 输出：5 -> 7 -> 3 -> 5 -> 3
 原因：34910 + 465 = 35375
 
 */

class Lesson2: NSObject {
    // MARK: - 运行
    class func run() -> Void {
        
        // MARK: 准备参数
        let length1 = 50000
        let length2 = 60000
//        let length1 = 6
//        let length2 = 5
        
        var array1: Array<Int> = []
        var array2: Array<Int> = []
        
        for _ in 0..<length1 {
            array1.append(Int(arc4random()) % 10)
        }
        
        for _ in 0..<length2 {
            array2.append(Int(arc4random()) % 10)
        }
        
        if array1.last == 0 {
            array1[length1 - 1] = 1
        }
        
        if array2.last == 0 {
            array2[length2 - 1] = 1
        }
        
//        debugPrint("原始1：\(array1) 原始2：\(array2)")
        
        // 计算时间参数
        var startTime: Double
        var endTime: Double
        var timeString: String
        
        // MARK: 开始计算
        // 1
        startTime = CFAbsoluteTimeGetCurrent()
        
        let _ = reason1(withArray1: array1, array2: array2)
        debugPrint("计算完成")
//        debugPrint("\(reason1(withArray1: array1, array2: array2))")
        
        endTime = CFAbsoluteTimeGetCurrent()
        timeString = String.init(format: "%.2f", (endTime - startTime) * 1000)
        debugPrint("代码执行时长：" + timeString + "毫秒")
        
        
        // MARK: 开始计算
        // 1
        startTime = CFAbsoluteTimeGetCurrent()
        
        let _ = reason2(withArray1: array1, array2: array2)
        debugPrint("计算完成")
//        debugPrint("\(reason1(withArray1: array1, array2: array2))")
        
        endTime = CFAbsoluteTimeGetCurrent()
        timeString = String.init(format: "%.2f", (endTime - startTime) * 1000)
        debugPrint("代码执行时长：" + timeString + "毫秒")
    }
    
    // MARK: - 解答
    
    // 最初版本
    class func reason1(withArray1 array1: [Int], array2: [Int]) -> [Int] {
        
        let maxLength = array1.count > array2.count ? array1.count : array2.count
        
        var currentInt: Int
        var nextAddInt: Int = 0
        var newArray: [Int] = []
        
        let array1Length = array1.count
        let array2Length = array2.count
        
        for i in 0 ..< maxLength {
            
            let num1: Int = i < array1Length ? array1[i] : 0
            let num2: Int = i < array2Length ? array2[i] : 0
            
            currentInt = num1 + num2 + nextAddInt
            nextAddInt = currentInt >= 10 ? 1 : 0
            currentInt = currentInt % 10
            newArray.append(currentInt)
        }
        
        if nextAddInt > 0 {
            newArray.append(nextAddInt)
        }
        
        return newArray
    }
    
    // 减少空间复杂度，快了2%~20%,大约10%
    class func reason2(withArray1 array1: [Int], array2: [Int]) -> [Int] {
        
        var longArray = array1.count >= array2.count ? array1 : array2
        let shortArray = array1.count < array2.count ? array1 : array2
        
        var currentInt: Int
        var nextAddInt: Int = 0
        
        for i in 0 ..< longArray.count {
            
            let numLong: Int = longArray[i]
            let numShort: Int = i < shortArray.count ? shortArray[i] : 0
            
            currentInt = numLong + numShort + nextAddInt
            nextAddInt = currentInt >= 10 ? 1 : 0
            currentInt = currentInt % 10
            longArray[i] = currentInt
        }
        
        if nextAddInt > 0 {
            longArray.append(nextAddInt)
        }
        
        return longArray
    }
    
}
